public class 重排链表 {

    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public void reorderList(ListNode head) {
        // 边界条件处理
        if (head.next == null || head.next.next == null) {
            return ;
        }
        // 判断奇偶性
        ListNode fast = head;
        ListNode slow = head;
        do {
            fast = fast.next.next;
            slow = slow.next;
        } while (fast != null && fast.next != null);
        // fast == null 偶 fast.next == null 奇

        // 后半部分头插法进行修改
        ListNode t = new ListNode();
        ListNode cur = slow.next; // slow 位置下一个元素开始逆序
        slow.next = null;
        while (cur != null) {
            ListNode next = cur.next; // 存储 slow 下一个节点
            cur.next = t.next; // 修改 slow 下一个为头插法的
            t.next = cur; // 头的下一个节点修改
            cur = next; // 更新 cur 的值
        }
        ListNode ans = new ListNode(0);
        ListNode cur1 = head;
        ListNode cur2 = t.next;
        ListNode cur3 = ans;
        while (cur1 != null) {
            // 先插第一个链表
            cur3.next = cur1;
            cur1 = cur1.next;
            cur3 = cur3.next;
            // 再插第二个链表
            if (cur2 != null) {
                cur3.next = cur2;
                cur2 = cur2.next;
                cur3 = cur3.next;
            }

        }

    }
}
